/*
*线性表的顺序存储及功能
*@author 寇戈
*@version 1.0 , 2021-9-28
*/
#include <iostream>
#include "myhead.h"
#include <malloc.h>

using namespace std;

#define LIST_INIT_SIZE 100
#define LIST_INCREAMENT 10

typedef struct
{
	//线性表的顺序表示
	ElemType *elem;
	int length;
	int listSize;
} SqList;

Status InitList_Sq(SqList &L)
{
	/*
	* 线性表的初始化
	* T(n)=O(1)
	*/
	L.elem = (ElemType *)malloc(sizeof(ElemType) * LIST_INIT_SIZE);
	if (!L.elem)
		exit(OVERFLOW);
	L.length = 0;
	L.listSize = LIST_INIT_SIZE;
	return OK;
}

Status ListGetElem_Sq(SqList L, int i, ElemType &e)
{
	/*
	* 读取元素操作
	* T(n)=O(1)
	*/

	//下标合法性判断
	if (i < 1 || i > L.length)
		return ERROR;

	e = L.elem[i - 1]; //将第i个元素赋值给e
	return OK;		   //返回成功状态
}

Status ListInsert_Sq(SqList &L, int i, ElemType e)
{
	/*
	* 插入元素操作
	* T(n)=O(n)
	*/

	//下标合法性判断
	if (i < 1 || i > L.length + 1)
		return ERROR;

	//长度超出列表大小处理
	if (L.length >= L.listSize)
	{
		ElemType *newbase = (ElemType *)realloc(L.elem, sizeof(ElemType) * (L.listSize + LIST_INCREAMENT)); //使用realloc函数为列表重新分配空间
		if (!newbase)
			exit(OVERFLOW); //若分配失败则退出程序
		L.elem = newbase;	//让列表首地址指向新分配的空间
		L.listSize += LIST_INCREAMENT;
	}

	//下标后元素整体后裔操作
	ElemType *q = L.elem + i - 1;
	for (ElemType *p = L.elem + L.length - 1; p >= q; p--)
		*(p + 1) = *p;

	*q = e;		//插入元素
	L.length++; //列表长度++
	return OK;	//返回成功状态
}

Status ListDelete_Sq(SqList &L, int i, ElemType &e)
{
	/*
	* 删除元素操作
	* T(n)=O(n)
	*/

	//下标合法性判断
	if (i < 1 || i > L.length)
		return ERROR;

	//下标后元素整体前移操作
	e = L.elem[i - 1];
	for (int *p = L.elem + i - 1; p < L.elem + L.length - 1; p++)
		*p = *(p + 1);

	L.length--;
	return OK;
}

int LocateElem_Sq(SqList L, ElemType e,
				  Status (*cmp)(ElemType, ElemType))
{
	/*
	* 查找某一元素下标,未找到则返回 0
	* T(n)=O(n)
	*/
	int i = 1;
	ElemType *p = L.elem;
	while (i <= L.length && !(*cmp)(*p++, e))
		i++;
	if (i <= L.length)
		return i;
	else
		return 0;
}

Status cmp_dev(ElemType a, ElemType b)
{
	/*
	* 判断两数相等的cmp函数(仅开发时使用)
	* T(n)=O(1)
	*/
	return a == b;
}

void ListShow_dev(SqList &L)
{

	/*
	* 读取元素操作(仅开发时使用)
	* T(n)=O(n)
	*/
	for (int i = 1; i <= L.length; i++)
	{
		ElemType mynum;
		ListGetElem_Sq(L, i, mynum);
		cout << mynum << " ";
	}
	cout << endl;
}

void MergeList(SqList La, SqList Lb, SqList &Lc)
{

	/*
	* 合并顺序表
	* 已知:La和Lb的元素按值非递减排列
	* 要求:归并后Lc的元素也按值非递减排列
	* T(n)=O(n)
	*/

	//初始化相关变量
	ElemType *pa = La.elem, *pa_last = La.elem + La.length - 1;
	ElemType *pb = Lb.elem, *pb_last = Lb.elem + Lb.length - 1;
	Lc.listSize = Lc.length = La.length + Lb.length;
	ElemType *pc = Lc.elem = (ElemType *)malloc(sizeof(ElemType) * Lc.length);
	if (!Lc.elem)
		exit(OVERFLOW);

	//归并:La和Lb最小长度内,两者的元素进行比较,小的先进入Lc
	while (pa <= pa_last && pb <= pb_last)
	{
		if (*pa < *pb)
			*pc++ = *pa++;
		/*
			*pc++ = *pa++;等同于:
			*pc=*pa;
			pc++;
			pa++;
		*/
		else
			*pc++ = *pb++;
	}

	//长度大的列表会有剩余元素,将这部分剩余元素插入Lc
	while (pa <= pa_last)
		*pc++ = *pa++;
	while (pb <= pb_last)
		*pc++ = *pb++;
}